/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package Practica6.practica;

import Practica6.spanningtrees.MinimumSpanningTree;
import Practica6.util.Graph;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

/**
 *
 * @author miguel
 */
public class ArbolDePesoMinimo implements MinimumSpanningTree {

    @Override
    public Graph getSpanningTree(Graph graph) {
        throw new UnsupportedOperationException("Not supported yet.");
    }

    public Graph Prim(Graph graph, MyVertex u) {

        MyGraph g = (MyGraph) graph;
        MyHeap<MyVertex> heap = new MyHeap<>(new CompareVertex());
        for (MyVertex v : (List<MyVertex>) g.getVertexList()) {
            v.setDistancia(Integer.MAX_VALUE);
            v.setPadre(null);
            heap.add(v);
        }
        u.setDistancia(0);
        while (!heap.esVacio()) {
            u = heap.getMin();
            for (MyVertex v : (List<MyVertex>) u.getNeighboursList()) {
                if (heap.esta(v) && v.getDistancia() > graph.getWeight(u, v)) {
                    v.setPadre(u);
                    v.setDistancia(graph.getWeight(u, v));
                }
            }
        }

        MyGraph g1 = new MyGraph();
        for (MyEdge e : (List<MyEdge>) g.getEdgesList()) {
            MyVertex source = ((MyVertex) e.getSource());
            MyVertex target = ((MyVertex) e.getTarget());
            if (source.getDistancia() < Integer.MAX_VALUE && target.getDistancia() < Integer.MAX_VALUE) {
                g1.getEdgesList().add(e);
                if (!g1.getVertexList().contains(source)) {
                    g1.getVertexList().add(source);
                }
                if (!g1.getVertexList().contains(target)) {
                    g1.getVertexList().add(target);
                }
            }
        }

        return g1;
    }

    public Graph Kruskal(Graph graph) {

        MyGraph g = (MyGraph) graph;
        MyDisjointSet mds = new MyDisjointSet(g.getVertexNum());
        for (MyVertex v : (List<MyVertex>) g.getVertexList()) {
            mds.makeSet(v.getIndex());
        }
        MyHeap<MyEdge> heap = new MyHeap<>(new CompareEdge());
        for (MyEdge e : (List<MyEdge>) g.getEdgesList()) {
            heap.add(e);
        }
        List<MyEdge> t = new ArrayList<>();
        while (t.size() <= g.getVertexNum() - 1) {
            MyEdge u = heap.getMin();
            int u1 = u.getSource().getIndex();
            int u2 = u.getTarget().getIndex();
            u1 = mds.findAgent(u1);
            u2 = mds.findAgent(u2);
            if (u1 != u2) {
                t.add(u);
                mds.union(u1, u2);
            }
        }

        MyGraph g1 = new MyGraph();
        for (MyEdge e : (List<MyEdge>) t) {
            g1.getEdgesList().add(e);
            MyVertex source = (MyVertex) e.getSource();
            MyVertex target = (MyVertex) e.getTarget();
            if (!g1.getVertexList().contains(source)) {
                g1.getVertexList().add(source);
            }
            if(!g1.getVertexList().contains(target)){
                g1.getVertexList().add(target);
            }
        }
        return g1;
    }

    /**
     * Clase de apoyo para MyHeap para comparar dos vértices
     */
    class CompareVertex implements Comparator<MyVertex> {

        @Override
        public int compare(MyVertex o1, MyVertex o2) {
            return o1.getDistancia() > o2.getDistancia() ? 1 : (o1.getDistancia() == o2.getDistancia() ? 0 : -1);
        }
    }

    class CompareEdge implements Comparator<MyEdge> {

        @Override
        public int compare(MyEdge o1, MyEdge o2) {
            return o1.getWeight() > o2.getWeight() ? 1 : (o1.getWeight() == o2.getWeight() ? 0 : -1);
        }
    }
}
